Integer Break [Tricky, DP]¶
Time: O(LogN); Space: O(1); medium
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers.
Return the maximum product you can get.
Example 1:
Input: num = 2
Output: 1
Explanation:
2 = 1 + 1; 1 * 1 = 1
Example 2:
Input: num = 10
Output: 36
Explanation:
10 = 3 + 3 + 4; 3 * 3 * 4 = 36
Notes:
There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.
Hints:
There is a simple O(n) solution to this problem.
You may check the breaking results of n ranging from 7 to 10 to discover the regularities.
1. Tricky solution¶
[1]:
class Solution1(object):
def integerBreak(self, num) -> int:
"""
:type num: int
:rtype: int
"""
if num < 4:
return num - 1
# Proof.
# 1. Let n = a1 + a2 + ... + ak, product = a1 * a2 * ... * ak
# - For each ai >= 4, we can always maximize the product by:
# ai <= 2 * (ai - 2)
# - For each aj >= 5, we can always maximize the product by:
# aj <= 3 * (aj - 3)
#
# Conclusion 1:
# - For n >= 4, the max of the product must be in the form of
# 3^a * 2^b, s.t. 3a + 2b = n
#
# 2. To maximize the product = 3^a * 2^b s.t. 3a + 2b = n
# - For each b >= 3, we can always maximize the product by:
# 3^a * 2^b <= 3^(a+2) * 2^(b-3) s.t. 3(a+2) + 2(b-3) = n
#
# Conclusion 2:
# - For n >= 4, the max of the product must be in the form of
# 3^Q * 2^R, 0 <= R < 3 s.t. 3Q + 2R = n
# i.e.
# if n = 3Q + 0, the max of the product = 3^Q * 2^0
# if n = 3Q + 2, the max of the product = 3^Q * 2^1
# if n = 3Q + 2*2, the max of the product = 3^Q * 2^2
res = 0
if num % 3 == 0: # n = 3Q + 0, the max is 3^Q * 2^0
res = 3 ** (num // 3)
elif num % 3 == 2: # n = 3Q + 2, the max is 3^Q * 2^1
res = 3 ** (num // 3) * 2
else: # n = 3Q + 4, the max is 3^Q * 2^2
res = 3 ** (num // 3 - 1) * 4
return res
[2]:
s = Solution1()
num = 2
assert s.integerBreak(num) == 1
num = 10
assert s.integerBreak(num) == 36
# for i in range(4, 12):
# print(i, s.integerBreak(i))
2. DP solution¶
[3]:
class Solution2(object):
"""
Time: O(N)
Space: O(1)
"""
def integerBreak(self, num) -> int:
"""
:type num: int
:rtype: int
"""
if num < 4:
return num - 1
# integerBreak(n) = max(integerBreak(n - 2) * 2, integerBreak(n - 3) * 3)
res = [0, 1, 2, 3]
for i in range(4, num + 1):
res[i % 4] = max(res[(i - 2) % 4] * 2, res[(i - 3) % 4] * 3)
return res[num % 4]
[4]:
s = Solution2()
num = 2
assert s.integerBreak(num) == 1
num = 10
assert s.integerBreak(num) == 36